package stu.day49;

import java.util.*;

public class hw3 {
    List<Integer> alist = new ArrayList<>();
    boolean falg = true;

    public int[] findOrder(int numCourses, int[][] prerequisites) {

        Map<Integer, List<Integer>> map = new HashMap<>();
        Map<Integer, Integer> map1 = new HashMap<>();  //入度
        List<Integer> node = new ArrayList<>();
        Map<Integer, Integer> map2 = new HashMap<>();

        for (int i = 0; i < numCourses; i++) {
            map1.put(i, 0);
        }


        for(int[] arr:prerequisites){
            map2.put(arr[0],0);
            map2.put(arr[1],0);

            int num = map1.getOrDefault(arr[0], 0);
            map1.put(arr[0], num);
            int num1 = map1.getOrDefault(arr[1], 0);
            map1.put(arr[1], num1+1);

            if(map.containsKey(arr[0])){
                map.get(arr[0]).add(arr[1]);
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(arr[1]);
                map.put(arr[0], list);
            }
        }


        for (Map.Entry<Integer, Integer> entry : map1.entrySet()) {
            if(entry.getValue() == 0){
                node.add(entry.getKey());
            }
        }


        alist.clear();
        for(Integer num:node){
            dfs(num,map,map1,map2);
        }

        Collections.reverse(alist);
        if (falg && (alist.size() == numCourses)){
            return alist.stream().mapToInt(i->i).toArray();
        }


        return new int[]{};

    }


    public void dfs(Integer num, Map<Integer, List<Integer>> map, Map<Integer, Integer> map1, Map<Integer, Integer> map2){

        List<Integer> l = map.get(num);
        if(map1.get(num)==0){
            alist.add(num);
        }
        map2.put(num,1);
        if(l == null){
            map2.put(num,2);
            return;
        }
        for(Integer i:l){
            if(map2.get(i)==1){
                falg = false;
                return;
            }
            if(map2.get(i)!=1){
                map1.put(i, map1.get(i)-1);
                if(map1.get(i)==0){
                    dfs(i,map,map1, map2);
                }
            }
        }
        map2.put(num,2);

    }

    public static void main(String[] args) {
        //        [[1,4],[2,4],[3,1],[3,2]],{2,4},{4,1}
        int[][] prerequisites = {{0,1},{1,0}};
        hw3 hw = new hw3();
        int[] arr =hw.findOrder(2, prerequisites);
        System.out.println(arr.length);
        System.out.println(hw.alist.size());
        for(int i:hw.alist){
            System.out.println(i);
        }
    }


}
